1. Field
The present disclosure relates generally to authentication. More specifically, the present disclosure relates to a method and system for facilitating throttling of interpolation-based authentication.
2. Related Art
In traditional cryptography, a frequently used primitive is Lagrange interpolation. Lagrange interpolation involves determining a least-degree polynomial that can interpolate a number of given data points. Lagrange interpolation has many uses in threshold cryptography, such as distributed generation of digital signatures, distributed recovery of secret keys (e.g., where the key has been lost or the key owner has been disabled), and access to a resource by one or more parties with required access information.
Using Lagrange interpolation, a threshold number of correctly selected values can be used to interpolate a polynomial and compute an intended output based on the Lagrange interpolation of the correctly selected values (e.g., the output of the Lagrange polynomial with a given evaluation input). This intended output can represent a secret that can be used for a subsequent authentication purpose, such as password recovery or generation of a digital signature. The idea behind using Lagrange interpolation for authentication is that fewer than a threshold number of such correct values would not carry any meaningful information about the intended output with the evaluation input. Furthermore, the user is not required to provide correct answers too all the challenge questions, so long as a sufficient number of correct answers can be provided to generate the correct interpolation.
The security guarantees of Lagrange interpolation do not exceed the entropy of the underlying shared secrets (i.e., the values needed to derive the polynomial and to compute the intended output). For example, when the polynomial is of a low degree, an adversary can exhaustively search the space of all possible assignments of values, perform interpolation for each such assignment, and then determine when a correct output has been obtained. It is also possible that the attacker can derive the correct answers to the challenge questions by using the trial-and-error method.
The above-described security limitation is particularly severe when the order of the Lagrange polynomial is low (i.e., the number of challenge questions is insufficient). The number of possible answers for a respective question may be relatively small, and the number of questions a typical user would be willing to answer can be relatively small. Thus, the total entropy will be low in these situations. In such situations, exhaustive-search-based or lattice-analysis-based attacks can present a higher risk to the security and privacy of the system.